package LeetCode;

import com.company.Tree.Tree;

import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}16:37
 */
public class LeetCode109 {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
          }
      }

    public TreeNode sortedListToBST(ListNode head) {
        // 方法一：将链表转化为数组,使用108的方法来进行一个计算，但是这样的话首先要遍历长度，之后就是还要遍历填值
        // 不能直接使用链表的原因：这里的链表没有直接的get（），而且就算有按照108的解法的话，每次都要进行遍历循环，会浪费很多时间
        if (head == null){
            return null;
        }
        if (head.next == null){
            return new TreeNode(head.val);
        }

        // 这里使用快慢指针确定链表的中间结点slow,pre就是中间
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 循环完后slow就指向链表的中点了
        // 之后就将链表以中点分为两块
        pre.next = null;// 这里很重要，pre是指向中点前一个点的，那么这个时候就将pre的下一个节点断开，使head链表中也发生断裂
        TreeNode node = new TreeNode(slow.val);
        node.left = sortedListToBST(head);// 此时head就像left一样 这里就是断裂过后的head链表
        node.right = sortedListToBST(slow.next);
        return node;
    }


    public TreeNode sortedListToBST2(ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null){
            return new TreeNode(head.val);
        }

        // 使用快慢指针来进行一个操作
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        TreeNode node = new TreeNode(slow.val);
        node.left = sortedListToBST2(head);
        node.right = sortedListToBST2(slow.next);
        return node;
    }

}
